// https://leetcode.cn/problems/maximum-width-of-binary-tree/description/

// 算法思路总结：
// 1. 广度优先搜索计算二叉树最大宽度
// 2. 使用pair记录节点和其在完全二叉树中的索引
// 3. 每层计算最左和最右节点的索引差
// 4. 左子节点索引=2*parent+1，右子节点索引=2*parent+2
// 5. 使用unsigned int防止索引溢出
// 6. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <queue>
#include <vector>
#include <algorithm>

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

TreeNode* buildTree(const vector<string>& nodes) 
{
    if (nodes.empty() || nodes[0] == "null") return nullptr;
    
    TreeNode* root = new TreeNode(stoi(nodes[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    
    while (!q.empty() && i < nodes.size()) 
    {
        TreeNode* current = q.front();
        q.pop();
        
        if (i < nodes.size() && nodes[i] != "null") 
        {
            current->left = new TreeNode(stoi(nodes[i]));
            q.push(current->left);
        }
        i++;
        
        if (i < nodes.size() && nodes[i] != "null") 
        {
            current->right = new TreeNode(stoi(nodes[i]));
            q.push(current->right);
        }
        i++;
    }
    
    return root;
}

class Solution 
{
public:
    typedef pair<TreeNode*, unsigned int> PTU;
    int widthOfBinaryTree(TreeNode* root) 
    {
        if (root == nullptr) return 0;

        queue<PTU> q;
        q.push({root, 0u});
        unsigned int ret = 0;

        while (!q.empty())
        {
            int sz = q.size();
            unsigned int l = q.front().second, r = l;
            for (int i = 0 ; i < sz ; i++)
            {
                auto [node, index] = q.front();
                q.pop();
                r = index;
                if (node->left) q.push({node->left, 2 * index + 1});
                if (node->right) q.push({node->right, 2 * index + 2});
            }
            ret = max(ret, r - l + 1);
        }

        return ret;
    }
};

int main()
{
    vector<string> nodes1 = {"1", "3", "2", "5", "3", "null", "9"};
    vector<string> nodes2 = {"1", "3", "2", "5", "null", "null", "9", "6", "null", "7"};

    Solution sol;

    auto root1 = buildTree(nodes1);
    auto root2 = buildTree(nodes2);

    cout << sol.widthOfBinaryTree(root1) << endl;
    cout << sol.widthOfBinaryTree(root2) << endl;

    return 0;
}